﻿//课程表
//已解答
//中等
//相关标签
//相关企业
//提示
//你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
//
//在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
//
//例如，先修课程对[0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
//请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
//
//
//
//示例 1：
//
//输入：numCourses = 2, prerequisites = [[1, 0]]
//输出：true
//解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
//示例 2：
//
//输入：numCourses = 2, prerequisites = [[1, 0], [0, 1]]
//输出：false
//解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
//
//
//提示：
//
//1 = numCourses = 2000
//0 = prerequisites.length = 5000
//prerequisites[i].length == 2
//0 = ai, bi  numCourses
//prerequisites[i] 中的所有课程对 互不相同
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int n = numCourses;
        //1.邻接表和入度
        unordered_map<int, vector<int>> edges;
        vector<int> in(numCourses, 0);

        //2.建图
        for (auto& e : prerequisites)
        {
            int a = e[0]; int b = e[1];//b->a
            edges[b].push_back(a);
            in[a]++;
        }


        //3.拓扑排序
        //(1).将入度为零的节点入队列
        queue<int> q;
        for (int i = 0; i < n; i++)
        {
            if (in[i] == 0)
                q.push(i);
        }

        //(2).bfs
        while (q.size())
        {
            int t = q.front();
            q.pop();

            //a.删除边
            for (auto e : edges[t])
            {
                in[e]--;
                if (in[e] == 0)
                {
                    q.push(e);
                }
            }
        }
        for (auto& e : in)
        {
            if (e != 0)
                return false;
        }
        return true;
    }
};